package zw_501_600.zw_575_分糖果;

import java.util.HashSet;

class Solution {

    public static void main(String[] args) {
        int[] candyType = {6, 6, 6, 6, 6};
        int candies = distributeCandies(candyType);
        System.out.println(candies);
    }

    /**
     * 根据题目给定的数据范围为 [-100,000, 100,000]，比较小，所以，我们可以声明一个数组来做为哈希表快速统计种类，
     * 并且，当种类的数量大于总数的一半时，我们就可以停止遍历了。
     *
     * @param candyType
     * @return
     */
    public static int distributeCandies(int[] candyType) {
        int count = 0;
        boolean[] map = new boolean[200001];
        for (int x : candyType) {
            if (!map[x + 100000]) {
                count++;
                map[x + 100000] = true;
                if (count >= candyType.length / 2) {
                    break;
                }
            }
        }
        return count;
    }


    /**
     * hashSet
     *
     * @param candyType
     * @return
     */
//    public static int distributeCandies(int[] candyType) {
//        int candyNum = candyType.length / 2;
//        HashSet<Integer> set = new HashSet<>();
//        for (int candy : candyType) {
//            if (set.add(candy) && set.size() >= candyNum) {
//                return candyNum;
//            }
//        }
//        return set.size();
//    }
}
